/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package batailledesardennes.util.geomFloat;

import batailledesardennes.util.FastMath;
import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author charly
 */
public class Polygon extends Shape {

    private List<Point> points;
    private Point center;
    private float signedArea;
    private float radius;
    private boolean counterClockWise;

    public Polygon() {
    }

    public Polygon(List<Point> points) {
        this(points, false);
    }

    public Polygon(List<Point> points, boolean copyPoints) {
        if (points == null || points.size() < 3) {
            throw new RuntimeException("Cant create polygon with less than 3 points");
        }
        this.points = new ArrayList<Point>(points.size());
        if (copyPoints) {
            for (Point p : points) {
                this.points.add(p.getCopy());
            }
        } else {
            this.points.addAll(points);
        }
        calcAll();
    }

    public Polygon(Point... points) {
        this(points, false);
    }

    public Polygon(Point[] points, boolean copyPoints) {
        if (points == null || points.length < 3) {
            throw new RuntimeException("Cant create polygon with less than 3 points");
        }
        this.points = new ArrayList<Point>(points.length);
        for (Point p : points) {
            if (copyPoints) {
                this.points.add(p.getCopy());
            } else {
                this.points.add(p);
            }
        }
        calcAll();
    }

    public Polygon(Polygon polygon) {
        this.points = new ArrayList<Point>(polygon.points.size());
        for (Point p : polygon.points) {
            points.add(p.getCopy());
        }
        signedArea = polygon.signedArea;
        radius = polygon.radius;
        center = polygon.center.getCopy();
        counterClockWise = polygon.counterClockWise;
    }

    /**
     *  Returns the closest intersection, if any, to pt0 (x0,y0)
     * Returns null otherwise
     * @param x0
     * @param y0
     * @param x1
     * @param y1
     * @return
     */
    @Override
    public Point getClosestIntersectionWithLine(float x0, float y0, float x1, float y1) {
        Point intersection = null;
        float distSq = -1;
        int nextIndex;
        for (int index = 0; index < points.size(); index++) {
            nextIndex = (index + 1 >= points.size() ? 0 : index + 1);
            Point p1 = points.get(index);
            Point p2 = points.get(nextIndex);
            Point intersect = GeomUtils.getLinesIntersection(x0, y0, x1, y1, p1.getX(), p1.getX(), p2.getX(), p2.getY());
            if (intersect == null) {
                continue;
            }
            float thisDistSq = intersect.distance(x0, y0);
            if (distSq < 0 || distSq > thisDistSq) {
                distSq = thisDistSq;
                intersection = intersect;
            }
        }
        return intersection;
    }

    /**
     * Returns closest point at a distance dist from polygon boundaries
     * @param x
     * @param y
     * @param dist
     * @return
     */
    @Override
    public Point getClosestPoint(float x, float y, float dist) {
        float distSq = -1;
        Point closestSegPt1 = null;
        Point closestSegPt2 = null;
        int nextIndex;
        for (int index = 0; index < points.size(); index++) {
            nextIndex = (index + 1 >= points.size() ? 0 : index + 1);
            Point p1 = points.get(index);
            Point p2 = points.get(nextIndex);
            float thisDistSq = GeomUtils.distToSeg(x, y, p1.getX(), p1.getY(), p2.getX(), p2.getY());
            if (distSq < 0 || thisDistSq < distSq) {
                distSq = thisDistSq;
                closestSegPt1 = p1;
                closestSegPt2 = p2;
            }
        }
        if (closestSegPt1 == null || closestSegPt2 == null) {
            return null;
        }
        Point closestPoint = GeomUtils.getClosestPointOnSegment(x, y, closestSegPt1.getX(), closestSegPt1.getY(),
                closestSegPt2.getX(), closestSegPt2.getY());
        if (dist > 0) {
            float angle = GeomUtils.findAngle(x, y, closestPoint.getX(), closestPoint.getY());
            closestPoint.translate(dist * FastMath.cos(angle), dist * FastMath.sin(angle));
        }
        return closestPoint;
    }

    @Override
    public Point getBoundPointFromCenterTowards(float x, float y) {
        float distToExtendOutTo = 2 * getRadius();
        float xCoord = getCenter().getX();
        float yCoord = getCenter().getY();
        float xDiff = x - getCenter().getX();
        float yDiff = y - getCenter().getY();
        if (xDiff == 0 && yDiff == 0) {
            yCoord += distToExtendOutTo;
        } else if (xDiff == 0) {
            yCoord += distToExtendOutTo * Math.signum(yDiff);
        } else if (yDiff == 0) {
            xCoord += distToExtendOutTo * Math.signum(xDiff);
        } else {
            xCoord += distToExtendOutTo * Math.abs(xDiff / (xDiff + yDiff)) * Math.signum(xDiff);
            yCoord += distToExtendOutTo * Math.abs(yDiff / (xDiff + yDiff)) * Math.signum(yDiff);
        }
        return getClosestIntersectionWithLine(getCenter().getX(), getCenter().getY(), xCoord, yCoord);
    }

    // Source code from: http://exaflop.org/docs/cgafaq/cga2.html
    //Subject 2.03: How do I find if a point lies within a polygon?
    //The definitive reference is "Point in Polyon Strategies" by Eric Haines [Gems IV] pp. 24-46. The code in the Sedgewick book Algorithms (2nd Edition, p.354) is incorrect.
    //The essence of the ray-crossing method is as follows. Think of standing inside a field with a fence representing the polygon. Then walk north. If you have to jump the fence you know you are now outside the poly. If you have to cross again you know you are now inside again; i.e., if you were inside the field to start with, the total number of fence jumps you would make will be odd, whereas if you were ouside the jumps will be even.
    //The code below is from Wm. Randolph Franklin <wrf@ecse.rpi.edu> with some minor modifications for speed. It returns 1 for strictly interior points, 0 for strictly exterior, and 0 or 1 for points on the boundary. The boundary behavior is complex but determined; | in particular, for a partition of a region into polygons, each point | is "in" exactly one polygon. See the references below for more detail
    //The code may be further accelerated, at some loss in clarity, by avoiding the central computation when the inequality can be deduced, and by replacing the division by a multiplication for those processors with slow divides.
    //References:
    //[Gems IV] pp. 24-46
    //[O'Rourke] pp. 233-238
    //[Glassner:RayTracing]
    @Override
    public boolean containsPoint(float x, float y) {
        Point prevPoint = points.get(points.size() - 1);
        int crossings = 0;
        for (Point p : points) {
            float px = p.getX();
            float py = p.getY();
            float prevY = prevPoint.getY();
            float prevX = prevPoint.getX();
            if (((prevY <= y && y < py) || (py <= y && y < prevY))
                    && (x < ((px - prevX) / (py - prevY) * (y - prevY) + prevX))) {
                crossings++;
            }
            prevPoint = p;
        }
        return (crossings % 2 != 0);
    }

    /**
     * Fills the given array with the bounds.
     * lefX, botY, rightX, topY
     * A new array is returned if the given one is null
     * or not big enough
     * @param bounds
     * @return
     */
    @Override
    public float[] getBounds(float[] bounds) {
        if (bounds == null || bounds.length < 4) {
            bounds = new float[4];
        }
        float leftX = Float.MAX_VALUE;
        float botY = Float.MAX_VALUE;
        float rightX = -Float.MAX_VALUE;
        float topY = -Float.MAX_VALUE;
        for (Point p : points) {
            if (p.getX() < leftX) {
                leftX = p.getX();
            }
            if (p.getY() < botY) {
                botY = p.getY();
            }
            if (p.getX() > rightX) {
                rightX = p.getX();
            }
            if (p.getY() > botY) {
                topY = p.getY();
            }
        }
        bounds[0] = leftX;
        bounds[1] = botY;
        bounds[2] = rightX;
        bounds[3] = topY;
        return bounds;
    }

    @Override
    public boolean intersects(Shape other) {
        if (other == null) {
            return false;
        }
        if (Polygon.class.isAssignableFrom(other.getClass())) {
            Polygon otherPol = (Polygon) other;
            int prevIndex = points.size() - 1;
            int prevIndexOther = otherPol.points.size() - 1;
            for (int index = 0; index < points.size(); index++) {
                Point point = points.get(index);
                Point prevPoint = points.get(prevIndex);
                for (int indexOther = 0; indexOther < otherPol.points.size(); indexOther++) {
                    Point pointOther = otherPol.points.get(indexOther);
                    Point prevPointOther = otherPol.points.get(prevIndexOther);
                    if (GeomUtils.getLinesIntersection(point, prevPoint, pointOther, prevPointOther) != null) {
                        return true;
                    }
                    prevIndexOther = indexOther;
                }
                prevIndex = index;
            }
        }
        return false;
    }

    @Override
    public boolean intersectsRect(float x, float y, float width, float height) {
        if (x + width < center.getX() - radius
                || x > center.getX() + radius
                || y + height < center.getY() - radius
                || y > center.getY() + radius) {
            return false;
        }
        for (int i = 0; i < points.size(); i++) {
            int nextI = (i + 1 >= points.size() ? 0 : i + 1);
            if (GeomUtils.linesIntersect(x, y, x + width, y, points.get(i).getX(), points.get(i).getY(), points.get(nextI).getX(), points.get(nextI).getY())
                    || GeomUtils.linesIntersect(x, y, x, y + height, points.get(i).getX(), points.get(i).getY(), points.get(nextI).getX(), points.get(nextI).getY())
                    || GeomUtils.linesIntersect(x, y + height, x + width, y + height, points.get(i).getX(), points.get(i).getY(), points.get(nextI).getX(), points.get(nextI).getY())
                    || GeomUtils.linesIntersect(x + width, y, x + width, y + height, points.get(i).getX(), points.get(i).getY(), points.get(nextI).getX(), points.get(nextI).getY())) {
                return true;
            }
        }
        double px = points.get(0).getX();
        double py = points.get(0).getY();
        if (px > x && px < x + width && py > y && py < y + height) {
            return true;
        }
        if (containsPoint(x, y)) {
            return true;
        }
        return false;
    }

    @Override
    public boolean containsRect(float x, float y, float width, float height) {
        if (x + width < center.getX() - radius
                || x > center.getX() + radius
                || y + height < center.getY() - radius
                || y > center.getY() + radius) {
            return false;
        }
        for (int i = 0; i < points.size(); i++) {
            int nextI = (i + 1 >= points.size() ? 0 : i + 1);
            if (GeomUtils.linesIntersect(x, y, x + width, y, points.get(i).getX(), points.get(i).getY(), points.get(nextI).getX(), points.get(nextI).getY())
                    || GeomUtils.linesIntersect(x, y, x, y + height, points.get(i).getX(), points.get(i).getY(), points.get(nextI).getX(), points.get(nextI).getY())
                    || GeomUtils.linesIntersect(x, y + height, x + width, y + height, points.get(i).getX(), points.get(i).getY(), points.get(nextI).getX(), points.get(nextI).getY())
                    || GeomUtils.linesIntersect(x + width, y, x + width, y + height, points.get(i).getX(), points.get(i).getY(), points.get(nextI).getX(), points.get(nextI).getY())) {
                return false;
            }
        }
        double px = points.get(0).getX();
        double py = points.get(0).getY();
        if (px > x && px < x + width && py > y && py < y + height) {
            return false;
        }
        if (containsPoint(x, y)) {
            return true;
        }
        return false;
    }

    @Override
    public boolean intersectsWithLineSegment(float x0, float y0, float x1, float y1) {
        int nextIndex;
        for (int index = 0; index < points.size(); index++) {
            nextIndex = (index + 1 >= points.size() ? 0 : index + 1);
            Point p1 = points.get(index);
            Point p2 = points.get(nextIndex);
            if (GeomUtils.linesSegmentsIntersect(p1.getX(), p1.getY(), p2.getX(), p2.getY(),
                    x0, y0, x1, y1)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public Polygon rotate(float angle, float x, float y) {
        for (Point p : points) {
            p.rotate(angle, x, y);
        }
        center.rotate(angle, x, y);
        return this;
    }

    @Override
    public Polygon translate(float x, float y) {
        for (Point p : points) {
            p.translate(x, y);
        }
        center.translate(x, y);
        return this;
    }

    @Override
    public Polygon translateTo(float x, float y) {
        float dx = x - center.getX();
        float dy = y - center.getY();
        return translate(dx, dy);
    }

    @Override
    public Polygon scale(float sx, float sy, float x, float y) {
        if (sx == 1 && sy == 1 && x == center.getX() && y == center.getY()) {
            return this;
        }
        for (Point p : points) {
            p.scale(sx, sy, x, y);
        }
        center.scale(sx, sy, x, y);
        calcSignedArea();
        calcRadius();
        return this;
    }

    public void reversePointOrder() {
        counterClockWise = !counterClockWise;
        List<Point> tempPoints = new ArrayList<Point>(points.size());
        for (int i = points.size() - 1; i >= 0; i--) {
            tempPoints.add(points.get(i));
        }
        points.clear();
        points.addAll(tempPoints);
    }

    public boolean isValidNoLineIntersections() {
        for (int i = 0; i < points.size(); i++) {
            int iPlus = (i + 1 >= points.size() ? 0 : i + 1);
            for (int j = i + 2; j < points.size(); j++) {
                int jPlus = (j + 1 >= points.size() ? 0 : j + 1);
                if (i == jPlus) {
                    continue;
                }
                Point intersect = GeomUtils.getLinesIntersection(points.get(i), points.get(iPlus), points.get(j), points.get(jPlus));
                if (intersect != null) {
                    return false;
                }
            }
        }
        return true;
    }

    public boolean isValidNoConsecutiveEqualPoint() {
        Point pointIBefore = (!points.isEmpty() ? points.get(points.size() - 1) : null);
        for (int i = 0; i < points.size(); i++) {
            Point pointI = points.get(i);
            if (pointI.getX() == pointIBefore.getX() && pointI.getY() == pointIBefore.getY()) {
                return false;
            }
        }
        return true;
    }

    public boolean isValidNoEqualPoint() {
        for (int i = 0; i < points.size(); i++) {
            Point pointI = points.get(i);
            for (int j = i + 1; j < points.size(); j++) {
                Point pointJ = points.get(j);
                if (pointI.getX() == pointJ.getX() && pointI.getY() == pointJ.getY()) {
                    return false;
                }
            }
        }
        return true;
    }

    @Override
    public Shape getCopy() {
        return new Polygon(this);
    }

    public void calcSignedArea() {
        signedArea = 0;
        int nextIndex;
        for (int i = 0; i < points.size(); i++) {
            nextIndex = (i + 1 >= points.size() ? 0 : i + 1);
            Point p0 = points.get(i);
            Point p1 = points.get(nextIndex);
            signedArea += (p0.getX() - p1.getX()) * (p1.getY() + (p0.getY() - p1.getY()) / 2);
        }
        counterClockWise = signedArea < 0;
    }

    public void calcCenter() {
        if (center == null) {
            center = new Point();
        }
        float cx = 0.0f;
        float cy = 0.0f;
        Point pointIBefore = (!points.isEmpty() ? points.get(points.size() - 1) : null);
        for (int i = 0; i < points.size(); i++) {
            Point pointI = points.get(i);
            double multiplier = (pointIBefore.getY() * pointI.getX() - pointIBefore.getY() * pointI.getX());
            cx += (pointIBefore.getX() + pointI.getX()) * multiplier;
            cy += (pointIBefore.getY() + pointI.getY()) * multiplier;
            pointIBefore = pointI;
        }
        cx /= (6 * getArea());
        cy /= (6 * getArea());
        if (counterClockWise == true) {
            cx *= -1;
            cy *= -1;
        }
        center.setX(cx);
        center.setY(cy);
    }

    public void calcRadius() {
        if (center == null) {
            calcCenter();
        }
        float maxRadiusSq = -1;
        int furthestPointIndex = -1;
        for (int i = 0; i < points.size(); i++) {
            float currentRadiusSq = (center.distanceSq(points.get(i)));
            if (currentRadiusSq > maxRadiusSq) {
                maxRadiusSq = currentRadiusSq;
                furthestPointIndex = i;
            }
        }
        radius = (center.distance(points.get(furthestPointIndex)));
    }

    public final void calcAll() {
        calcSignedArea();
        calcCenter();
        calcRadius();
    }

    @Override
    public float getPerimeter() {
        float perimeter = 0;
        for (int i = 0; i < points.size() - 1; i++) {
            perimeter += points.get(i).distance(points.get(i + 1));
        }
        perimeter += points.get(points.size()).distance(points.get(0));
        return perimeter;
    }

    public float getSignedArea() {
        return signedArea;
    }

    @Override
    public float getArea() {
        return Math.abs(signedArea);
    }

    @Override
    public Point getCenter() {
        return center;
    }

    public boolean isCounterClockWise() {
        return counterClockWise;
    }

    public List<Point> getPoints() {
        return points;
    }

    @Override
    public float getRadius() {
        return radius;
    }
}
